package com.xhh.learning.record.algorithm.search;

import java.util.LinkedList;

/**
 * 类名： DFS
 * 描述：
 * 公司： 北京海鑫科金高科技股份有限公司
 * 作者： Administrator
 * 版本： V1.0
 * 创建时间:  2019/6/10 14:56
 * 最后修改时间:  2019/6/10 14:56
 */
public class DFS {

    public static void main(String[] args) {
        BFS.Graph g = new BFS.Graph(8);
        g.addEdge(0, 1);
        g.addEdge(0, 3);
        g.addEdge(2, 1);
        g.addEdge(4, 1);
        g.addEdge(4, 3);
        g.addEdge(4, 5);
        g.addEdge(4, 6);
        g.addEdge(2, 5);
        g.addEdge(5, 7);
        g.addEdge(6, 7);

        boolean[] visited = new boolean[g.v];
        int[] prev = new int[g.v];
        for (int i = 0; i < g.v; i++) {
            prev[i] = -1;
        }

        dfs(g, prev, visited, 0, 6);
        print(prev, 0, 6);
    }

    static boolean found = false;

    public static void dfs(BFS.Graph graph, int[] prev, boolean[] visited, int s, int t) {
        if (found) {
            return;
        }

        if (s == t) {
            found = true;
            return;
        }

        visited[s] = true;

        for (int i = 0; i < graph.adj[s].size(); i++) {
            Integer q = graph.adj[s].get(i);
            if (!visited[q]) {
                prev[q] = s;
                dfs(graph, prev, visited, q, t);
            }
        }
    }

    public static void print(int[] prev, int s, int t) {
        if (prev[t] != -1 && s != t) {
            print(prev, s, prev[t]);
        }
        System.out.print(t + " ");
    }


}
